package first.forHuaWei.codeTop;

/**
 * @ClassName LC42
 * @description:
 * @author: 荣燊
 * @create: 2021-09-13 10:51
 **/
public class LC42 {
    // 剑指 Offer 42. 连续子数组的最大和
    // 动态规划，dp[i]:以nums[i]结尾的最大子串值
    // dp[i] = dp[i-1] + num[i]; 判断dp[i-1]是否大于0
    public static int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int result = nums[0];
        for (int i=1; i<n; i++) {
            if (dp[i-1] >= 0) {
                dp[i] = dp[i-1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] ints = {-1, 2, 1};
        System.out.println(maxSubArray(ints));
    }
}
